/**
     * 一个简单的图和图算法
     * @constructor
     */
function Graph() {
    this.vertices = 0    //顶点
    this.edges = 0       //边
    this.adjMap = {}    //定义map
    this.adjMapAll = {}    //定义map
    this.markedMap = {}  //标记是否已访问 false为未访问 true为访问过了
    this.addEdge = addEdge  //添加顶点
    this.removeEdge = removeEdge //移除顶点
    this.show = show  //显示顶点
    this.dfs = dfs      //深度优先搜索
    this.bfs = bfs      //广度优先搜索
    this.edgeToMap = {}  //从一个顶点到下一个顶点的所有边
    this.hasPathTo = hasPathTo //是否有路径
    this.pathTo = pathTo //最短路径
    this.allPathTo = allPathTo //所有路径
    this.removeOneInArr = removeOneInArr //移除数组某个元素
}

//添加顶点
function addEdge(v, m) {
    this.markedMap[v] = false
    this.markedMap[m] = false
    this.adjMap[v] = this.adjMap[v] ? this.adjMap[v].indexOf(m)>-1?this.adjMap[v]:this.adjMap[v].concat([m]) : [m]
    this.adjMap[m] = this.adjMap[m] ? this.adjMap[m].indexOf(v)>-1?this.adjMap[m]:this.adjMap[m].concat([v]) : [v]
    this.vertices++
    this.edges++
}

//移除顶点
function removeEdge(v, m) {
  if (this.adjMap[v]) {
    this.removeOneInArr(this.adjMap[v], m)
  }
  if (this.adjMap[m]) {
    this.removeOneInArr(this.adjMap[m], v)
  }
  if (this.adjMap[v] && this.adjMap[v].length == 0) {
    delete this.adjMap[v]
    delete this.markedMap[v]
    this.vertices--
    this.edges--
  }
  if (this.adjMap[m] && this.adjMap[m].length == 0) {
    delete this.adjMap[m]
    delete this.markedMap[m]
    this.vertices--
    this.edges--
  }
}

//移除数组某个元素
function removeOneInArr(arr, obj) {
  var index = arr.indexOf(obj)
  if (index > -1) {
    arr.splice(index, 1)
  }
}

//显示顶点
function show() {
    for (let i in this.markedMap) {
        let edges = ''
        for (let j = 0; j < this.vertices; j++) {
            if (this.adjMap[i] && this.adjMap[i][j]) {
                edges += this.adjMap[i][j] + ' '
            }
        }
    }
}

//深度优先搜索（有待研究）
function dfs(v) {
    this.markedMap[v] = true
    if (this.adjMap[v] !== undefined) {
      //
    }
    for (let w in this.adjMap[v]) {
        let current = this.adjMap[v][w]
        if (!this.markedMap[current]) {
            this.dfs(current)
        }
    }
}

//广度优先搜索
function bfs(v) {
    for(let key in this.markedMap){
        this.markedMap[key] = false;
    }
    let queue = []
    this.markedMap[v] = true
    queue.push(v)
    while (queue.length > 0) {
        let s = queue.shift()
        for (let w in this.adjMap[s]) {
            let current = this.adjMap[s][w]
            if (!this.markedMap[current]) {
                this.markedMap[current] = true
                this.edgeToMap[current] = s
                queue.push(current)
            }
        }
    }
}

//是否有路径
function hasPathTo(v) {
    return this.markedMap[v]
}
//最短路径
function pathTo(s, v) {
    let source = s
    if (!this.hasPathTo(v)) return undefined
    let path = []
    for (let i = v; i != source; i = this.edgeToMap[i]) {
        if (!i) {
            break;
        }
        path.push(i)
    }
    path.push(source)
    return path
}
//所有路径
function allPathTo(s, v) {
    let queuee = []
    let allpath = []
    queuee.push([s])
    while (queuee.length > 0) {
      let path = queuee.pop(0)
      let node = path[path.length-1]
      if (node == v) {
        allpath.push(path)
      }
      let graphNode = this.adjMapAll[node] || []
      for (var i =0;i<graphNode.length;i++) {
        let new_path = [].concat(path)
        new_path.push(graphNode[i])
        queuee.push(new_path)
      }
    }
    return allpath
  }

export const getGraph = () => {
    return new Graph();
}
/*
let graph = new Graph()
graph.addEdge('a', 1)
graph.addEdge(1, 2)
graph.addEdge(0, 4)
graph.addEdge(2, 3)
graph.addEdge(3, 4)
graph.addEdge(3, 'a')
graph.addEdge('b', 'a')
graph.addEdge('b', 8)
graph.addEdge(4, 5)
graph.addEdge(5, 6)
graph.addEdge(6, 7)
graph.addEdge(7, 8)
graph.addEdge(7, 'c')
graph.show()
// graph.dfs('a') //暂未实现
graph.bfs('a')
let paths = graph.pathTo('a', 'c')
let str = ''
while (paths.length > 0) {
    if (paths.length > 1) {
        str += paths.pop() + '->'
    } else {
        str += paths.pop()
    }
}
*/
